On the complexity of orthogonal compaction☆☆Research supported in part by the CNR Project “Geometria Computazionale Robusta con Applicazioni alla Grafica ed al CAD”, by the ESPRIT LTR Project 20244 (ALCOM-IT), and by “Progetto Algoritmi per Grandi Insiemi di Dati: Scienza e Ingegneria”, MURST Programmi di Ricerca di Rilevante Interesse Nazionale.

AbstractWe consider three closely related optimization problems, arising from the graph drawing and the VLSI research areas, and conjectured to be NP-hard, and we prove that, in fact, they are NP-complete. Starting from an orthogonal representation of a graph, i.e., a description of the shape of the edges that does not specify segment lengths or vertex positions, the three problems consist of providing an orthogonal grid drawing of it, while minimizing the area, the total edge length, or the maximum edge length, respectively.This result confirms a long surviving conjecture of NP-hardness, justifies the research about applying sophisticated, yet possibly time consuming, techniques to obtain optimally compacted orthogonal grid drawings, and discourages the quest for an optimally compacting polynomial-time algorithm